class Solution {
public:
  bool wordBreak(string s, vector<string>& wordDict) {

    set<string> stringSet;
    for(string &word : wordDict){
      stringSet.insert(word);
    }
    // dp[i]表示dp[0 : i - 1]能被分解为字典里的字符串
    bool dp[s.length() + 1];
    memset(dp, false, sizeof(dp));
    dp[0] = true;

    for(int i = 1; i <= s.length(); ++i){
      for(int j = i - 1; j >= 0; --j){
        // dp[i]取决于两点：
        // 1.s[0 : j - 1]是否能分解，即dp[j]是否是true
        // 2.s[j : i - 1]是否能分解为字典里的字符串
        string sub = s.substr(j, i - j);
        if(dp[j] && stringSet.count(sub)){
          dp[i] = true;
          break;
        }
      }
    }

    return dp[s.length()];

  }
};